package main

/**
A B C D E
C B A D E

1->2->3->4->5
1.目的是翻转子链表，首先找到待翻转子链表的前驱节点prev(同时为简化考虑逻辑，我们设立一个dummynode,将其Next指向链表首节点dn->1->2->3...）
2.对待翻转在子链表进行翻转，共需要翻转n-m次 (m到n共n-m+1个节点，共需要n-m+1-1次翻转)
3.返回翻转后的链表头节点dn->Forward
![](http://cdn.bsummer.cn/20210316014837.png)

找准prev,current 即可反转
*/
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Forward *ListNode
 * }
 */
import . "local/algorithm/util"

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	// 使用dummynode简化问题解决
	dn := &ListNode{Val: 0, Next: head}
	prev := dn

	// 找到第m节点前驱节点 对于有dummy节点的链表来说，第m个节点需要翻m次，从dn节点开始，执行m-1次循环到达第m个节点的前驱节点
	for count := 0; count < m-1; count++ {
		prev = prev.Next
	}

	// 整个翻转过程中每次翻转2个节点，期间pre和last(pre为子串前驱节点，last为子串尾节点)始终没有变动，变动的是pre.Forward,last.Forward
	// 翻转后初始子链头结点会变为尾结点
	// tmp与last意义不同，tmp是prev的后继节点，last是子串尾节点，每次变动后last.Forward = last.Forward.Forward
	last := prev.Next
	for i := 0; i < n-m; i++ { // m,n之间一共n-m+1个数，需要执行n-m+1-1次翻转
		tmp := prev.Next
		prev.Next = last.Next      // last.Next是本次要翻转的节点
		last.Next = last.Next.Next // 尾结点连接后续节点
		prev.Next.Next = tmp
	}
	return dn.Next
}

func main() {
	list := GenerateLinkedList([]int{1, 2, 3, 4, 5})
	newList := reverseBetween(list, 1, 3)
	PrintLinkedList(newList)
}

func reverseBetween(head *ListNode, m, n int) *ListNode {
	dn := &ListNode{Next: head}
	prev := dn
	for i := 0; i < m-1; i++ {
		prev = prev.Next
	}

	last := prev.Next
	for i := 0; i < m-n; i++ {
		tmp := prev.Next
		prev.Next = last.Next
		last.Next = last.Next.Next
		prev.Next.Next = tmp
	}

	return dn.Next
}
